package priv.conceit.study.leetcode.medium;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Stack;

/**
 * 编号144
 * 二叉树的前序遍历
 * <a href="https://leetcode-cn.com/problems/binary-tree-preorder-traversal/"></a>
 * 给定一个二叉树，返回它的 前序 遍历。
 * <p>
 * 示例:
 * [1,null,2,3]
 * 1
 * \
 * 2
 * /
 * 3
 * 输出: [1,2,3]
 * <p>
 * 中序遍历
 * 访问顺序 根->根->右
 * <p>
 * <p>
 * 1-递归
 * 2-非递归 使用栈数据结构
 *
 * @author conceit
 * @since 1.0.0, 2019/7/23
 */
@SuppressWarnings("all")
public class BinaryTreePreorderTraversal {

	public static void main(String[] args) {

	}


	/**
	 * 前序遍历-迭代
	 * 前序遍历 需要借助 栈 数据结构
	 * 如果右节点不为空 右节点先入栈-先入后出
	 * 如果左结点不为空 左结点再入栈-后入先出
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> preOrderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		if (Objects.isNull(root)) {
			return result;
		}
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);

		while (!stack.empty()) {
			TreeNode curTreeNode = stack.pop();
			result.add(curTreeNode.val);
			if (Objects.nonNull(curTreeNode.right)) {
				stack.push(curTreeNode.right);
			}
			if (Objects.nonNull(curTreeNode.left)) {
				stack.push(curTreeNode.left);
			}
		}
		return result;
	}

	/**
	 * 前序遍历-递归
	 * 递归内声名变量 会增加空间复杂度
	 * 提交代码时 新建辅助方法，将list放入形参，无返回值，减少运行时间
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> preOrderRecursion(TreeNode root) {

		List<Integer> result = new ArrayList<>();
		if (Objects.nonNull(root)) {
			preOrderRecursionHelper(root, result);
		}
		return result;
	}

	/**
	 * 递归助手
	 *
	 * @param root
	 * @param result
	 */
	public void preOrderRecursionHelper(TreeNode root, List<Integer> result) {
		if (Objects.nonNull(root)) {
			result.add(root.val);
			preOrderRecursionHelper(root.left, result);
			preOrderRecursionHelper(root.right, result);
		}
	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}


}
